/*
/**
 * You have a set of n integers each in the range 0 ... K. Partition these integers into two subsets such that you minimize 
 * |S1 - S2|, 
 *where S1 and S2 denote the sums of the elements in each of the two subsets.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <fstream>
#include <iostream>


using namespace std;

int BalancedPartition(const vector<int> &input)
{
	int sum = 0;
	for (int i = 0; i < input.size(); i++)
		sum += input[i];

	//generate dp table
	vector<vector<bool>> dp(input.size(), vector<bool>(sum+1, false));

	dp[0][0] = true;
	dp[0][input[0]] = true;

	for (int i = 1; i < input.size(); i++) {
		for (int j = 0; j <= sum; j++) {
			dp[i][j] = dp[i-1][j] || (j >= input[i]) && dp[i-1][j - input[i]];
		}
	}

	for (int i = sum/2; i>=0; i--) {
		if (dp[input.size()-1][i] == true)
			return i;
	}
}

int main()
{
	int input[] = {1,5,7,8,9,6,3,11,20,17};
	vector<int> data(input, input + sizeof(input)/sizeof(int));
	int sum = BalancedPartition(data);

	return 1;
}